﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics.Tracing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//79. 单词搜索
//给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

//单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
public class Solution79
{
    public string myword;
    public bool isExist;
    public int m;
    public int n;
    bool[][] visited;
    public bool Exist(char[][] board, string word)
    {
        m=board.Length;
        n = board[0].Length;
        myword = word;

         visited =new bool[m][]; 
        for(int i = 0; i < m; i++)
        {
            visited[i]=new bool[n];
        }
        //DFS遍历
        string path = null;
        //IList<char> path =new List<char>();

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
              bool flag=  DFS(board, 0, i, j);//开头位置不确定，遍历所有的开头
                //只要返回false，就是不匹配

                if (flag)
                {
                    return flag;
                }

            }
        }
        


        return false;
    }

    private bool DFS(char[][] board, int wordIndex, int row,int col)//这个方法是传递字符串进行比较，单独比较每一个字符
    {
      
       
        if (row >= m || col >= n|| row < 0 || col < 0)
        {
            return false;
        }
      
        if (visited[row][col]) {
            //访问过的不访问
            return false;
        }
        if (myword[wordIndex] != board[row][col])//不相等
        {
            return false;
        }
        else
        {
            if (wordIndex == myword.Length - 1)
            {

                //相等,并且是最后一位
                return true;
            }
        }
        //相等,并且不是最后一位，继续判断
        //加入当前的字符


        visited[row][col]=true;

       

        //DFS(board, wordIndex+1, row+1, col);//向下

        ////回溯操作
         
        //DFS(board, wordIndex + 1, row-1, col);//向上

        //DFS(board, wordIndex + 1, row, col + 1);//右
        //DFS(board, wordIndex + 1, row, col - 1);//左

        //当前层的结果是由下一层决定的。
        bool res= DFS(board, wordIndex + 1, row + 1, col)|| DFS(board, wordIndex + 1, row - 1, col)|| DFS(board, wordIndex + 1, row, col + 1) || DFS(board, wordIndex + 1, row, col - 1);

        //if (visited[row][col])
        //{
        //    //访问过的不访问
        //    return false;
        //}
        //回溯
        visited[row][col]=false ;
        return res;
    }
    private void DFS2(char[][] board, string path,int row,int col)//这个方法是传递字符串进行比较，单独比较每一个字符
    {
       if(path== myword)
        {
            isExist = true;
            return;
        }
        if (row >= m || col >= n)
        {
            return;
        }
        if (row <0 || col <0)
        {
            return;
        }
        if (visited[row][col]) {
            //访问过的不访问
            return;
        }

        //加入当前的字符

        string newpath =path+board[row][col];
        visited[row][col]=true;
        Console.WriteLine(newpath);
        DFS2(board,new string( newpath), row+1, col);//向下

        //回溯操作
         
        DFS2(board, new string(newpath), row-1, col);//向上

        DFS2(board, new string(newpath), row, col + 1);//右
        DFS2(board, new string(newpath), row, col - 1);//左


    }
}

class Program79
{
    static void Main79(string[] args)
    {
        char[][] board = [['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'], 
        ['A', 'D', 'E', 'E']];

        //[["C", "A", "A"],
        //["A", "A", "A"],
        //["B", "C", "D"]]
        Solution79 solution = new Solution79();
        string word = "ABCCED";
      bool res=  solution.Exist(board, word);
        Console.WriteLine("res"+res);

    }
}